/**
 * @file   BinarySearchTree.h
 * @author Shao <student@student>
 * @date   Tue Nov  2 22:37:14 2021
 * 
 * @brief  
 * 
 * 
 */

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include<iostream>
using namespace std;
 
template <typename Comparable>
class BinarySearchTree
{
public:
	BinarySearchTree() :m_root(nullptr){}
	BinarySearchTree(const BinarySearchTree & rhs )
	{
		m_root = clone(rhs.m_root);
	}
	~BinarySearchTree()
	{
		makeEmpty();
	}
 
	/**
	* Find the minimum value in the tree and implement recursion by calling private findMin.
	*/
	const Comparable & findMin() const
	{
		return findMin(m_root)->element;
	}
 
	/**
	* Find the maximum value in the tree and implement recursion by calling private findMax.
	*/
	const Comparable & findMax() const
	{
		return findMax(m_root)->element;
	}
 
	/**
	* Return true when x is found, otherwise return false. 
	*/
	bool contains(const Comparable & x ) const
	{
		return contains(x, m_root);
	}
 
	/**
	* Determine whether the tree is empty.
	*/
	bool isEmpty() const
	{
		return m_root == nullptr;
	}
 
	/**
	* Traverse the tree again (middle order, because middle order can guarantee sequential output).
	*/
	void printTree(ostream & out= cout) const
	{
		if (isEmpty())
			out << "Empty tree!" << endl;
		else
			printTree(m_root, out);
	}
 
	/**
	* Empty tree.
	*/
	void makeEmpty()
	{
		makeEmpty(m_root);
	}
 
	/**
	* Insert x into the tree and ignore if it is repeated.
	*/
	void insert(const Comparable &x)
	{
		insert(x, m_root);
	}
 
	/**
	* Remove x from the tree, If x is not in the tree, do nothing. 
	*/
	void remove(const Comparable &x)
	{
		remove(x, m_root);
	}
 
	/**
	* Copy.
	*/
	const BinarySearchTree & operator= (const BinarySearchTree &rhs)
	{
		if (this != &rhs)
		{
			BinaryNode *tmp = clone(rhs.m_root);
			makeEmpty();
			m_root = tmp;
		}
		return *this;
	}
 
 
private:
	struct BinaryNode{
		Comparable element;
		BinaryNode *left;
		BinaryNode *right;
		
		BinaryNode(const Comparable &theElement,
			BinaryNode *lt,
			BinaryNode *rt)
			: element(theElement), left(lt), right(rt) {}
	};
 
	BinaryNode *m_root;
 
	/**
	* Insert the element x in the tree t and do nothing if it is repeated.
	*/
	void insert(const Comparable &x, BinaryNode * &t) const
	{
		if (t == nullptr)
			t = new BinaryNode(x, nullptr, nullptr);
		else if (x < t->element)
			insert(x, t->left);
		else if (t->element < x)
			insert(x, t->right);
		else
			; // Indicates that if x is found in the tree, nothing will be done.
	}
 
	/**
	* Delete element x in tree t.
	*/
	void remove(const Comparable &x, BinaryNode * &t) const
	{
		if (t == nullptr)
			return; 
		if (x < t->element)
			remove(x, t->left);
		else if (t->element < x)
			remove(x, t->right);
		else if (t->left != nullptr &&
		t->right != nullptr)
		{
			t->element = findMin(t->right)->element;
			remove(t->element, t->right);
		}
		else
		{
			BinaryNode * oldNode = t;
			t = (t->left != nullptr) ? t->left : t->right;
			delete oldNode;
		}
	}
 
	/**
	* Find the smallest element by recursive method.
	*/
	BinaryNode * findMin(BinaryNode *t) const
	{
		if (t == nullptr)
			return nullptr;
		if (t->left == nullptr)
			return t;
		return findMin(t->left);
	}
 
	/**
	* Find the largest element, through the loop method.
	*/
	BinaryNode * findMax(BinaryNode *t) const
	{
		if (t != nullptr)
			while (t->right != nullptr)
				t = t->right;
		return t;
	}
 
	/**
	* Find whether x is in the tree t by traversing.
	*/
	bool contains(const Comparable &x, BinaryNode * t) const
	{
		if (t == nullptr) // The termination condition of the element not found in the traversal
			return false;
		else if (x < t->element)
			return contains(x, t->left);
		else if (t->element < x)
			return contains(x, t->right);
		else 
			return true;
	}
 
	/**
	* Empty tree.
	*/
	void makeEmpty(BinaryNode * &t)
	{
		if (t != nullptr)
		{
			makeEmpty(t->left);
			makeEmpty(t->right);
			delete t;
		}
		t = nullptr;
	}
 
	/**
	* Print subtree.
	*/
	void printTree(BinaryNode *t, ostream & out) const
	{
		if (nullptr != t)
		{
			printTree(t->left, out);
			out << t->element << endl;
			printTree(t->right, out);
		}
	}
 
	/**
	* Copy subtree.
	*/
	BinaryNode * clone(BinaryNode *t) const
	{
		if (t == nullptr)
			return nullptr;
 
		return new BinaryNode(t->element, clone(t->left), clone(t->right));
	}
 
};
#endif
